The ACO Seminar (2024–2025)

The first goal of this talk is to describe some recent progress (in joint work with Jeff Kahn and Jinyoung Park) on the "Second" Kahn-Kalai Conjecture (KKC2), the original conjecture on graph containment in $G_{n,p}$ that motivated what is now the Park-Pham Theorem (PPT). KKC2 says that $p_c(H)$, the threshold for containing a graph $H$ in $G_{n,p}$, satisfies $p_c(H)=O(p_E \log n)$, where $p_E$ is the smallest $p$ such that the expected number of copies of any subgraph of $H$ is at least one. In other words, for this class of problems, the expectation threshold $q$ in PPT can be replaced by the smaller $p_E$. We show that $q\lt O(p_E \log^2 n)$ (implying $p_c(H)=O(p_E \log^3 n)$ via PPT). Time-permitting, the second portion of the talk will discuss some hopes for and failed attempts at sharpening PPT and KKC2.